Chihik's Blog

An Ac a day, keeps the doctor away!

P6055 [RC-02] GCD

发布于 2020-09-12 | 分类于 莫比乌斯反演 | 3分钟 | 471字数

这道题的反推还是挺有意思的。

∑i=1n∑j=1n∑p=1⌊nj⌋∑q=1⌊nj⌋[(i,j)=1][(p,q)=1]\sum_{i=1}^n\sum_{j=1}^n\sum_{p=1}^{\lfloor \frac{n}{j} \rfloor}\sum_{q=1}^{\lfloor \frac{n}{j} \rfloor}[(i,j)=1][(p,q)=1]

阅读全文 »

SP26108 TRENDGCD - Trending GCD

发布于 2020-09-12 | 6分钟 | 905字数

∑i=1n∑j=1mij(i,j)μ2((i,j))\sum_{i=1}^n\sum_{j=1}^m ij (i,j)\mu^2((i,j))

∑k=1min⁡(n,m)∑i=1n∑j=1m[(i,j)=k]ijkμ2(k)\sum_{k=1}^{\min(n,m)}\sum_{i=1}^n\sum_{j=1}^m [(i,j)=k]ij k\mu^2(k)

阅读全文 »

P3977 [TJOI2015]棋盘

发布于 2020-09-10 | 分类于 矩阵乘法 、 状压dp | 5分钟 | 809字数

你得知道题目下表是从 00 开始编号，那么每个棋子只能控制与它距离不大于 11 的行。

所以只需压当前这一行的状态，令 dp(i,S)dp(i,S) 表示前 ii 行棋子，第 ii 的摆放状态为 SS 的方案。

那么有转移：

阅读全文 »

CF208E Blood Cousins

发布于 2020-09-07 | 分类于 树上启发式合并(dsu on tree) | 4分钟 | 617字数

和 uu 拥有共同的 kk 级祖先的点数就是 uu 的 kk 级祖先的 kk 级儿子的数量 −1-1.

再转换一下就是以 uu 的 kk 级祖先为根的子树内深度为 depu+kdep_u+k 的点的个数−1-1。

然后用 cntdcnt_d 表示深度为 dd 的点数，直接 dsu on tree\text{dsu~on~tree} 即可。

阅读全文 »

UVA12177 First Knight

发布于 2020-09-05 | 分类于 期望dp 、 高斯消元 | 4分钟 | 580字数

设 dp(i,j)dp(i,j) 表示由 (i,j)(i,j) 走到 (n,m)(n,m) 的期望步数。

那么显然有转移：

dp(i,j)=1+(up(i,j)×dp(i+1,j)+down(i,j)×dp(i−1,j)+left(i,j)×dp(i,j−1)+right(i,j)×dp(i,j+1))dp(i,j)=1+(up(i,j) \times dp(i+1,j) + down(i,j) \times dp(i-1,j) + left(i,j) \times dp(i,j-1) + right(i,j) \times dp(i,j+1))

阅读全文 »

CF685B Kay and Snowflake

发布于 2020-09-05 | 分类于 重心 、 倍增 | 2分钟 | 388字数

这道题应该算是 CSP2019 树的重心\text{CSP2019 树的重心} 的前置知识了吧。可惜之前我并没有做过。

对于一棵以 uu 为根的子树，它的重心只可能在点 uu 或 以点 uu 的重儿子为根的子树中。

那么类比 lca\text{lca} 倍增父亲，树的重心倍增重儿子。

阅读全文 »

UVA10859 Placing Lampposts

发布于 2020-09-05 | 分类于 树形dp | 3分钟 | 487字数

nn 个点 mm 条边的无向无环图，其实就是一个森林。

题目要求最小化两个量：灯数和只被一边照亮的边数。

一个做法是定义两个 dpdp 数组，分别表示最小灯数和在灯数最小情况下的一边被照亮的最小边数。

阅读全文 »
0%